import java.util.ArrayList;
import java.util.List;

//leetcode 784 字母大小写全排列
public class Test5 {
    List<String> ret;
    StringBuilder path;
    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(s, 0);
        return ret;
    }

    private void dfs(String s, int pos) {
        if (pos == s.length()) {
            ret.add(path.toString());
            return;
        }

        char tmp = s.charAt(pos);
        path.append(tmp);
        dfs(s, pos + 1);
        path.deleteCharAt(pos);

        if (tmp < '0' || tmp > '9') {
            char ch = change(tmp);
            path.append(ch);
            dfs(s, pos + 1);
            path.deleteCharAt(pos);
        }
    }

    private char change(char c) {
        if (c >= 'a' && c <= 'z') return c -= 32;
        else return c += 32;
    }
}
